Экономия на мыле

Ограничение времени1 секунда
Ограничение памяти256 Мб
Вводстандартный ввод или input.txt
Выводстандартный вывод или output.txt

Снижение расходов в ресторанном деле — залог успешного бизнеса.

Каждое утро дозатор вместимостью W W миллилитров полностью заполняется мылом. В течение дня им пользуются посетители. После каждого нажатия из дозатора выливается X X миллилитров жидкости. После любого использования можно долить в дозатор любое целое число миллилитров воды, не превышая при этом его вместимость W W .

Если мыло окажется слишком сильно разбавлено водой или если в дозаторе будет меньше X X миллилитров жидкости, посетители это заметят, рассердятся и перестанут ходить в ресторан. Поэтому перед каждым использованием дозатора в нём должно быть хотя бы X X миллилитров жидкости, а доля мыла во всей жидкости должна быть не меньше A B \frac{A}{B} .

Требуется найти максимальное количество нажатий на дозатор, которое можно обеспечить так, чтобы никто из посетителей не рассердился.

Формат ввода

В единственной строке записаны четыре целых числа W W , X X , A A , B B ( 1 ≤ W ≤ 3 ⋅ 1 08 , 1 ≤ X ≤ W , 1 ≤ A ≤ B , 1 ≤ B ≤ 3 ⋅ 1 08 ) (1 \leq W \leq 3\cdot 10^8, 1 \leq X \leq W, 1 \leq A \leq B, 1 \leq B \leq 3\cdot 10^8) .

Формат вывода

Выведите одно целое число — максимальное количество нажатий, которое вы можете обеспечить.

Система оценивания

В задаче 50 50 наборов тестовых данных. За каждый тест, на который был найден правильный ответ, начисляется 2 балла.

Гарантируется, что решения, корректно работающие при W , X , A , B ≤ 10 W,X,A,B \leq 10 , наберут не менее 30 30 баллов.

Также гарантируется, что решения, корректно работающие на тестах, ответы в которых не превосходят 4 ⋅ 1 05 4 \cdot 10^5 , наберут не менее 60 60 баллов.

Пример 1

ВводВывод
2 1 1 2

3

Пример 2

ВводВывод
2 1 2 3

2

Пример 3

ВводВывод
5 2 1 7

6

Примечания

В первом примере вместимость дозатора равна 2 2 миллилитрам, за одно использование из него выливается 1 1 миллилитр жидкости, а доля мыла должна быть не меньше 1 2 \frac{1}{2} .

После первого использования можно долить 1 1 миллилитр воды. Тогда доля мыла станет равна 1 2 \frac{1}{2} , и после этого доливать воду уже не получится. Оставшихся 2 2 миллилитров жидкости с долей мыла 50 % 50\% хватит ещё на 2 2 использования.

Таким образом, ответ равен 3 3 .